\section{Problema 1}

\subsection{Enunciado}
   Mi hermana tenía un precioso collar hecho de coloridas cuentas multicolores. Cada cuenta mantenía con la siguiente
un color en común en el punto de enlace. 
   Un día el collar se rompió y las cuentas quedaron esparcidas por el piso. Mi hermana hizo todo lo posible para juntarlas
todas. Ahora me vino a pedir ayuda.
   Quiere saber si es posible rehacer el collar con todas las N cuentas que tiene y en el mismo lugar que el collar original.
De ser posible volver a armarlo quiere además quiere saber el orden.

\paragraph{}
   Resolver el problema en orden estrictamente menor a $O(N^{2} + C)$, donde C es la cantidad de colores posibles de las
perlas y N es el mencionado anteriormente.


\subsection{Modelado del problema}

	Modelaremos la situación con un multigrafo-pseudografo no dirigido:
\begin{enumerate}
	\item Los nodos representarán los diferentes colores presentes en las cuentas encontradas.
	\item Las aristas representarán las cuentas encontradas: cada extremo de una arista representa uno de los colores de la cuenta.
\end{enumerate}

El grafo es no dirigido, porque según el enunciado lo importante es que dos cuentas 
coincidan en color por un extremo, sin importar cuál, ni cómo estén ubicadas en el collar.

Es un multigrafo, porque no hay restricciones sobre la cantidad de cuentas que tengan un par de colores
iguales entre ellas.

Y es un pseudografo, porque nada impide que los extremos de una misma cuenta tengan el mismo color.

De ahora en más, lo llamaremos simplemente \textit{grafo}.

\paragraph{}
Al momento de leer los datos de entrada, desconocemos la cantidad máxima de colores distintos.
Usamos, entonces, el número (color) más grande presente en la entrada como referencia.

Una vez que hayamos contado la cantidad de veces que aparece cada color, podrían haber algunos que
no hayan aparecido en ningún momento. En lugar de interpretarlos como nodos aislados, a los fines
del problema contarán como etiquetas no presentes: podrían contar como colores de cuentas que se
perdieron pero no influyen en que podamos armar un collar con las que ya fueron encontradas
(ver ejemplos en la sección Casos de prueba).

\paragraph{}
Finalmente, el problema que se está modelando es: \textbf{circuito euleriano}. Determinar si dicho grafo es euleriano y, en caso positivo, devolver una lista de aristas
que conforman el circuito. Si no, un mensaje predefinido.


\begin{figure}[h!]
	\centering
	\renewcommand{\figurename}{Ejemplo}
	\caption{El segmento de collar utilizado en el enunciado representado como grafo}
	\subfloat[Grafo] {
	\begin{tikzpicture}
		\SetVertexNormal[Shape = circle,
							FillColor  = white]
		%\SetVertexNoLabel
		\SetUpEdge[lw         = 1pt,
						color      = black,
						labelcolor = white,
						labeltext  = black,
						labelstyle = {sloped,draw,text=black}]
						
		\Vertex[x=2, y=3]{R}
		\Vertex[x=4, y=0]{V}
		\Vertex[x=0, y=0]{A}
		
		\tikzstyle{EdgeStyle}=[bend left]
		\Edges(R,V)
		\Edges(V,A)
		\Edges(A,R)
		\tikzstyle{EdgeStyle}=[bend right]
		\Edges(R,V)
	\end{tikzpicture}
	}
\end{figure}


% \begin{figure}[h]
% 	\centering
% 	\renewcommand{\figurename}{Ejemplo}
% 	\caption{El segmento de collar utilizado en el enunciado representado como grafo}
% 	\subfloat[Grafo] {
% 	\begin{tikzpicture}
% 		\SetVertexNormal[Shape = rectangle,
% 							FillColor  = white]
% 		%\SetVertexNoLabel
% 		\SetUpEdge[lw         = 1pt,
% 						color      = black,
% 						labelcolor = white,
% 						labeltext  = black,
% 						labelstyle = {sloped,draw,text=black}]
% 						
% 		\Vertex[x=0, y=0, L=V$|$V]{n1}
% 		\Vertex[x=2, y=0, L=V$|$R]{n2}
% 		\Vertex[x=4, y=0, L=R$|$A]{n3}
% 		\Vertex[x=6, y=0, L=A$|$M]{n4}
% 		\Vertex[x=8, y=0, L=M$|$R]{n5}
% 		\Vertex[x=10, y=0, L=R$|$A]{n6}
% 		\Vertex[x=12, y=0, L=A$|$V]{n7}
% 		
% 		\Edges(n1,n2)
% 		\Edges(n2,n3)
% 		\Edges(n3,n4)
% 		\Edges(n4,n5)
% 		\Edges(n5,n6)
% 		\Edges(n6,n7)
% 		
% 		\tikzstyle{EdgeStyle}=[bend left]
% 		\Edges(n7,n1)
% 	\end{tikzpicture}
% 	}
% \end{figure}
% 
% \begin{figure}[h!]
% 	\centering
% 	\renewcommand{\figurename}{Ejemplo}
% 	\caption{El segmento de collar utilizado en el enunciado representado como grafo}
% 	\subfloat[Grafo] {
% 	\begin{tikzpicture}
% 		\SetVertexNormal[Shape = rectangle,
% 							FillColor  = white]
% 		%\SetVertexNoLabel
% 		\SetUpEdge[lw         = 1pt,
% 						color      = black,
% 						labelcolor = white,
% 						labeltext  = black,
% 						labelstyle = {sloped,draw,text=black}]
% 						
% 		\Vertex[x=0, y=0, L=V$|$V]{n1}
% 		\Vertex[x=1, y=0, L=V, style={shape=circle, fill= orange}]{n2}
% 		\Vertex[x=2, y=0, L=V$|$R]{n3}
% 		\Vertex[x=3, y=0, L=R, style={shape=circle, fill= orange}]{n4}
% 		\Vertex[x=4, y=0, L=R$|$A]{n5}
% 		\Vertex[x=5, y=0, L=A, style={shape=circle, fill= orange}]{n6}
% 		\Vertex[x=6, y=0, L=A$|$M]{n7}
% 		\Vertex[x=7, y=0, L=M, style={shape=circle, fill= orange}]{n8}
% 		\Vertex[x=8, y=0, L=M$|$R]{n9}
% 		\Vertex[x=9, y=0, L=R, style={shape=circle, fill= orange}]{n10}
% 		\Vertex[x=10, y=0, L=R$|$A]{n11}
% 		\Vertex[x=11, y=0, L=A, style={shape=circle, fill= orange}]{n12}
% 		\Vertex[x=12, y=0, L=A$|$V]{n13}
% 		\Vertex[x=6, y=-1, L=V, style={shape=circle, fill= orange}]{n14}
% 		
% 		\Edges(n1,n2)
% 		\Edges(n2,n3)
% 		\Edges(n3,n4)
% 		\Edges(n4,n5)
% 		\Edges(n5,n6)
% 		\Edges(n6,n7)
% 		\Edges(n7,n8)
% 		\Edges(n8,n9)
% 		\Edges(n9,n10)
% 		\Edges(n10,n11)
% 		\Edges(n11,n12)
% 		\Edges(n12,n13)
% 		
% 		\tikzstyle{EdgeStyle}=[bend left]
% 		\Edges(n13,n14)
% 		\Edges(n14,n1)
% 	\end{tikzpicture}
% 	}
% \end{figure}

\subsubsection{Problema $\Rightarrow$ Modelo}
En el problema tenemos dos posibles soluciones, que se encuentren todas las cuentas y se pueda volver
a formar el collar o que se hayan perdido cuentas y no sea posible. Vamos a analizar los dos casos
por separado:

\paragraph{A. No es posible volver a formar el collar:}
Que el collar no se pueda volver a formar se debe que no existe una forma de ubicar las cuentas encontradas
de modo que cada cuenta comparta un color con la siguiente y uno con la anterior. Esto se puede deber a dos
razones, hay una cuenta que no se puede ubicar ya que no existe otra que comparta el mismo color o a que
se pueden armar pequeños collares pero no se pueden juntar entre sí para formar el collar completo.

En el primer caso tendríamos entonces una cuenta que no tiene pareja y en esta situación tendríamos un color
que aparece un número impar de veces. Esto en nuestro grafo se ve reflejado como un nodo que tiene un grado
impar (ya que las cuentas son aristas y hay una cantidad impar de cuentas con este color) y esto implica que
no exista un ciclo euleriano en el grafo. Por lo tanto en este caso no existe tampoco una solución en el modelo.

En el segundo caso tendríamos secciones formadas por una o más cuentas que cumplen los requisitos del enunciado
(el caso de una cuenta sería una con sus dos colores iguales). Entre dos de estas secciones no hay colores en común
ya que si los hubiera entonces podríamos separar un par de cuentas de cada sección con el color que comparte
y unir las secciones formando una más grande que contradice lo que planteamos como hipotesis. Estas secciones se
representan en nuestro modelo como diferentes componentes conexas ya que una arista de nuestro modelo representa
una cuenta del problema y al no existir cuentas que se puedan usar para unir dichas secciones en el problema tampoco
existen aristas que se puedan usar para unir las componentes conexas en el modelo. Por lo tanto el grafo no es conexo
y esto implica que no se pueda encontrar un circuito euleriano en él.

\paragraph{B. Se pudo formar el collar:}
Si se encontró una solución al problema entonces existe una forma de poner las cuentas de manera que dos
cuentas contiguas estén unidas por el mismo color y que eso forme un circuito. Ahora, si tomamos este circuito
formado y colocamos un nodo por cada hilo que une dos cuentas con el color por el que están
unidas y luego remplazamos cada cuenta por una arista, estaremos formando el circuito euleriano que es
solución del modelo. Este es un circuito en nuestro modelo ya que tiene como aristas las cuentas del collar
y como nodos los diferentes colores presentes en dichas cuentas. Por lo tanto, siempre que se encuentre una solución
se podrá crear un circuito euleriano que la represente y sea solución en nuestro modelo.

\subsubsection{Modelo $\Rightarrow$ Problema}
Hay dos posibles soluciones para el modelo, que el grafo sea euleriano o que no. Analizaremos estos
dos casos por separados a continuación

\paragraph{A. Caso grafo no euleriano:}
Si no hemos podido encontrar un circuito euleriano en el grafo, fue porque: no era conexo y/o 
tenía algún nodo con grado impar.

\paragraph{I. Caso algún nodo con grado impar:}
Existe algún nodo en el grafo que tiene grado impar. Como cada nodo representa un color que aparece
en las cuentas encontradas, un nodo de grado impar representa un color que se presenta en un número
impar de cuentas. Al tener un número impar de cuentas con dicho color, no es posible unir las
cuentas que poseen ese color, ya que habría una que no tiene pareja. Por lo tanto, no es posible armar un
collar con las cuentas encontradas respetando los requisitos del problema.


\paragraph{II. Caso no conexo:}
Existe algún par de nodos $v$ y $w$, con grados d($v$)$>$ 0 y d($w$)$>$ 0, tales que no existe un camino
entre $v$ y $w$. Un camino es secuencia de aristas, cada una con un vértice en común con la siguiente.

Como los nodos representan colores y cada arista una cuenta, existen dos colores tales que no hay una sucesión 
de cuentas conectadas entre sí con la siguiente por un color en común, que formen una porción del collar.
Por lo tanto, no puede armarse un collar completo con las cuentas encontradas.


\paragraph{B. Caso grafo euleriano:}
Si no cae en ninguno de los casos anteriores, es que tenemos un circuito euleriano $S$ = \{ $e_{1},...,e_{N}$ \}.
Verifica que:
\begin{enumerate}
	\item Para cada arista $e$ de E(grafo), $e$ está en $S$.
	\item Para $i \in [2,...,N-1]$, $e_{i}$ tiene en común con $e_{i-1}$ uno de sus extremos, y el otro con $e_{i+1}$
	\item En particular, $e_{N}$ tiene un extremo en común con $e_{N-1}$ y el otro con $e_{1}$. Y $e_{1}$
	tiene un extremo en común con $e_{N}$ y el otro con $e_{2}$. 
\end{enumerate}

Las aristas representan cuentas, por lo tanto, del item (1) se deriva que se usaron todas las cuentas encontradas
para armar la secuencia.

Como además, los nodos representan colores, y cada cuenta tiene dos colores, del item (2) se desprende que en la cadena
armada, cada cuenta comparte dos colores, uno con cada cuenta contigua.

Por el item (3), esa cadena de cuentas que fue armada puede unirse por los extremos de igual modo que las cuentas intermedias
para formar el collar pedido.



\subsection{Pseudoc\'odigo}

\paragraph{Funcionamiento:}

	A grandes rasgos, primero evalúa que se cumpla la caracterización de un grafo euleriano: todos los nodos de grado par,
y que sea conexo.
	Si valen, partiendo de un nodo cualquiera de grado mayor que 0, seguimos adyacencias
no visitadas (sin importar el criterio de elección) hasta llegar al nodo del que partimos.
A medida que ibamos recorriendo las aristas no visitadas, las agregábamos a una lista y decrementábamos en 1
el grado a los nodos involucrados.

Si el nodo al que llegábamos quedaba con grado mayor que 0, lo agregábamos a una cola con su etiqueta y 
la posición dentro de la lista para insertar un nuevo circuito.

Una vez que llegamos al nodo inicial, continuamos con el siguiente nodo de la cola, a recorrer de modo
análogo. Si tenía grado 0, comenzamos con el siguiente. Los circuitos que vayamos armando los agregamos en la posición
de la lista (un puntero o un iterador) que encolamos junto con la etiqueta del nodo (dentro de una estructura).

\begin{algorithm}[H]
\caption{armarGrafo(Lista $cuentas$)}
\begin{algorithmic}[1]
	\STATE $max$ $\leftarrow$ $0$
	\STATE 
	\FOR{\textbf{cada} Cuenta $c$ \textbf{en} $cuentas$}
		\STATE $max$ $\leftarrow$ maximo($max$, maximo(color1($c$),color2($c$)))
	\ENDFOR
	\STATE
	\STATE $grafo$ $\leftarrow$ Grafo(max)
	\STATE
	\FOR{\textbf{cada} Cuenta $c$ \textbf{en} $cuentas$}
		\STATE ponerArista($grafo$, color1($c$), color2($c$))
	\ENDFOR
	\STATE
	\RETURN $grafo$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[H]
\caption{esEuleriano(Grafo $grafo$)}
\begin{algorithmic}[1]
	\IF{$\neg$esConexo($grafo$)}
		\RETURN \FALSE
	\ENDIF
	\STATE
	\FOR{\textbf{cada} Nodo $n$ \textbf{en} nodos($grafo$)}
		\IF{grado($n$, $grafo$) $\%$ 2 $\neq$ 0}
			\RETURN \FALSE
		\ENDIF
	\ENDFOR
	\STATE
	\RETURN \TRUE
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[H]
\caption{circuitoEuleriano(Grafo $grafo$)}
\begin{algorithmic}[1]
	\STATE $circuito$ $\leftarrow$ Lista$<$Artista$>$
	\STATE $artistas\_visitadas$ $\leftarrow$ Vector$<$ Par $<$Artista, Booleano$>$ $>$
	\STATE $adyacencias$ $\leftarrow$ Vector$<$ Lista$<$Artista$>$ $>$
	\STATE
	\FOR{\textbf{cada} Arista $c$ \textbf{en} aristas($grafo$)}
		\STATE agregar($aristas\_visitadas$, $< arista$, \FALSE $>$)
		\STATE
		\STATE agregar($adyacencias[$nodo1($arista$)$]$, $arista$)
		\STATE agregar($adyacencias[$nodo2($arista$)$]$, $arista$)
	\ENDFOR
	\STATE
	\STATE $grados$ $\leftarrow$ grados($grafo$)
	\STATE $circuitos$ $\leftarrow$ Cola$<$ Par$<$Nodo, Entero$>$ $>$
	\STATE encolar($circuitos$, $<$primero(nodos($grafo$)), 1$>$)
	\STATE
	\WHILE{$\neg$vac\'io($circuitos$)}
		\STATE Par $temp \; \leftarrow$ desencolar($circuitos$)
		\STATE Nodo $nodocentral \; \leftarrow$ primero($temp$)
		\STATE Entero $pos \; \leftarrow$ segundo($temp$)
		\STATE $circuitoArmado \leftarrow$ \FALSE
		\STATE $nodo \; \leftarrow$ $nodocentral$
		\STATE
		\WHILE{$\neg circuitoArmado$}
			\IF{grado($nodo$) $>$ 0}
				\STATE Arista $arista$ $\leftarrow$ primeraNoVisitada(adyacencias$[nodo]$)
				
				\IF{$\neg arista$}
					\STATE $circuitoArmado$ $\leftarrow$ \TRUE
				\ELSE
					\STATE grados$[$nodo1($arista$)$]--$
					\STATE grados$[$nodo2($arista$)$]--$
					
					\STATE
					\IF{grados$[nodo]$ $>$ 0}
						\STATE encolar($circuitos$, $<nodo,\; pos>$)
					\ENDIF
					
					\STATE
					\STATE marcarVisitada($aristas\_vistadas$, $arista$)
					\STATE insertarEn($circuito$, $nodo$, $pos$)
					
					\STATE
					\IF{nodo1($arista$) $=$ $nodo$}
						\STATE nodo $\leftarrow$ nodo2($arista$)
					\ELSE
						\STATE nodo $\leftarrow$ nodo1($arista$)
					\ENDIF
					\STATE
					\IF{$nodo$ $=$ $nodocentral$}
						\STATE  $circuitoArmado$ $\leftarrow$ \TRUE
					\ENDIF
				\ENDIF
			\ELSE
				\STATE $circuitoArmado$ $\leftarrow$ \TRUE
			\ENDIF
		\ENDWHILE
	\ENDWHILE
	\STATE
	\RETURN $circuito$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[H]
\caption{resolver(Lista $cuentas$)}
 \begin{algorithmic}[1]
	\STATE Grafo $grafo$ $\leftarrow$ armarGrafo($cuentas$)
	\STATE
	\IF{esEuleriano($grafo$)}
		\STATE imprimir circuitoEuleriano($grafo$)
	\ELSE
		\STATE imprimir ``Some beads may be lost''
	\ENDIF
 \end{algorithmic}
\end{algorithm}

\subsection{An\'alisis de complejidad}
Para la implementación del grafo usamos una estructura que cumple con las siguientes complejidades:
\begin{itemize}
	%\item ponerNodo(Grafo $grafo$) $\rightarrow$ $O(1)$
	\item maximo(enteros $a$,$b$) $\rightarrow$ $O(1)$
	\item ponerArista(Grafo $grafo$) $\rightarrow$ $O(1)$
	\item nodos(Grafo $grafo$) $\rightarrow$ $O(\#V) = O(C)$
	\item adyacencias(Grafo $grafo$) $\rightarrow$ $O(\#E) = O(N)$
\end{itemize}


\subsubsection{armarGrafo}
En armarGrafo tenemos:
\begin{itemize}
 \item La primera línea tiene costo $O(1)$
 \item En el primer ciclo (l\'ineas $3$ a $6$) recorre todas las cuentas ($N$) y por cada una hace dos operaciones en que tardan $O(1)$ (comparar buscando el máximo entre dos números)
 \item La variable $max$ contiene el valor $C$
 \item En la línea 7, crea un grafo con $C$ nodos, todos de grado 0. Implícitamente, crea un vector $grados$ de $C$ posiciones inicializadas en 0. El costo es $O(C)$.
 \item En el segundo ciclo (l\'ineas $9$ a $11$) recorre todas las cuentas ($N$) y por cada una hace una operaci\'on en que tarda $O(1)$.
\end{itemize}
En total:
$$O(1) + \sum_{1}^{N}2O(1) + O(C) + \sum_{1}^{N}O(1) = O(N) + O(C) + O(N) \in O(N + C)$$

\subsubsection{esEuleriano}
En esEuleriano tenemos:
\begin{itemize}
 \item En la guarda del \textbf{si} (l\'inea $1$) se llama a esConexo que no es más que hace un \textbf{BFS} sobre el grafo y comprobar que se marcaron todos los nodos $O(N + C)$.
 \item En el ciclo dentro del \textbf{sino} (l\'ineas $5$ a $9$) recorre todos los nodos ($C$) y por cada uno hace una operaci\'on en que tarda $O(1)$.
\end{itemize}
En total:
$$O(N + C) + \sum_{1}^{C}O(1) = O(N + C) + O(C) \in O(N + C)$$


\subsubsection{circuitoEuleriano}
En la primera parte circuitoEuleriano (l\'ineas $1$ a $15$) tenemos:
\begin{itemize}
 \item En la l\'inea $1$ crear la lista $circuito$ tarda $O(1)$.
 \item Crear el vector $aristas\_visitadas$ tarda $O(N)$.
 \item Crear el vector $adyacencias$ tarda $O(N)$ ya que se crea un vector de $N$ elementos y cada elemento se incializa con una lista vac\'ia $O(1)$.
 \item Crear el vector $grados$ tarda $O(C)$. Crea una copia del vector homónimo que usa el grafo.
 \item El ciclo de las l\'ineas $5$ a $10$ recorre todas las aristas del grafo $O(N)$ y por cada una realiza operaciones que tardan $O(1)$, por lo tanto $\in O(N)$.
 \item La llamada a grados (l\'inea $12$) tarda $O(C)$.
 \item Crear la cola $circuitos$ (l\'inea $13$) tarda $O(1)$ y encolar un elmento (l\'inea $14$) tambi\'en.
\end{itemize}

En la segunda parte, no se indica explícitamente la cantidad de iteraciones. Y además, cada iteración puede tener efectos
colaterales que cambien la complejidad en la siguiente. Por eso haremos un análisis de la complejidad de cada línea, pero
explicaremos menos formalmente cuál es la complejidad total.
\begin{itemize}
 \item La guarda del ciclo (línea 16) evalúa si la cola $circuitos$ está vacía: $O(1)$
 \item Las líneas 17,18,19,20 y 21 tienen costo $O(1)$
 \item El siguiente ciclo evalúa si se armó un circuito, desde el nodo desencolado $nodoactual$
 \item Complejidad SI(1); si aún quedan aristas incidentes a $nodo$
 \begin{itemize}
	\item En la línea 25. primeraNoVisitada tiene complejidad $O(1)$ amortizada.
	
	\textbf{PROP1: se visita una arista exactamente dos veces: una para marcarla y otra para ver si fue visitada}
	\item Complejidad SI(2)
	
	\begin{itemize}
			\item Líneas 26 y 27: comparación y asignación de variables primitivas tiene complejidad $O(1)$
	\end{itemize}
	\item Complejidad SINO(2).
 
	\begin{itemize}
			\item Líneas 29 y 30: obtener un extremo y decrementar variables primitivas tiene complejidad $O(1)$
			\item Líneas 32 a 34: la comparación tiene costo $O(1)$ y si ingresa, encolar tiene costo $O(1)$ (push\_back de la STL), porque lo que agrega es un par ordenado de tamaño constante.
			\item La función marcarVisitada tiene costo $O(1)$, pues realiza una asignación de bool.
			
			\textbf{PROP2: por cada arista se decrementa el grado a los dos extremos}
			\item La función insertarEn tiene costo $O(1)$ (es list::insert, de la STL).
			\item En las líneas 39 a 43, se realizan comparaciones con costo $O(1)$.
			\item En las líneas 45 a 47, se realizan comparaciones y asignaciones con costo $O(1)$.
			
			\textbf{PROP3: si llega a nodoactual, se sale del ciclo y se formó un circuito de tamaño $K_i$}
	\end{itemize}
\end{itemize}
 \item Complejidad SINO(1); si ya se visitaron todas las aristas incidentes en el nodo desencolado.
 	\begin{itemize}
			\item Línea 50: La asignación de booleanos tiene costo $O(1)$ 
			
			\textbf{PROP4: el costo del ciclo es $O(1)$ si el nodo quedó con grado 0. Sólo se sale}
	\end{itemize}
 
\end{itemize}


Por PROP3, el ciclo más interno itera $K_1$ veces. Por PROP2, se reduce el grado de $2*K_1$ vértices, pero sólo de aquellos que podían decrementarse.

Si el nodo quedó con grado 0, por PROP4 se sale del ciclo. De eso se deriva que no se decrementará de más.

El ciclo principal se termina cuando la cola de nodos con aristas sin revisar se vacía. Si el nodo era incidente a aristas no visitadas aún, se entrará en un ciclo que iterará $K_2$ veces.
Decrementando el grado de $2*K_2$ vértices.

Se encola un nodo, cuando se llega por una arista no visitada. Hay $N$ aristas, pero sólo se podrá marcarla desde uno de los nodos.

En cada iteración se marcan $K_i$ aristas. Por PROP1, se visitan las aristas exactamente dos veces, por lo tanto, en total se visitan:

$$\sum_{i=0}^{tot.ciclos} 2*K_i = 2*N$$

Por lo tanto, la complejidad es del orden de $O(N)$.

Cuando existe un circuito euleriano, la cantidad de nodos $C$ está acotado por la cantidad de aristas $N$, porque si no, no habría circuito.


\subsubsection{primeraNoVisitada}
En el contexto del ciclo, la complejidad de obtener la siguiente arista no visitada es $O(1)$ amortizada.

Se recorre la lista de adyacencias y si el primer elemento fue visitado, quiere decir que la complejidad ya fue pagada al obtener la adyacencia
en la lista del otro extremo. Se lo elimina y continúa con el siguiente.



\subsubsection{resolver}
En resolver tenemos:
\begin{itemize}
 \item La llamada a armarGrafo (l\'inea $1$) tarda $O(N + C)$.
 \item La guarda del \textbf{si} (l\'inea $3$) llama a esEuleriano que tarda $O(N + C)$.
 \item El imprimir y la llamada a circuitoEuleriano dentro del  \textbf{si} (l\'inea $4$) tardan $O(N + C)$.
\end{itemize}
En total:
$$O(N + C) + O(N + C) + O(N + C) = 3O(N + C) \in O(N + C)$$



\subsection{Casos de prueba}

\newtheorem{caminoeuleriano}{Teorema}
\begin{caminoeuleriano}
Sea G=(V,E) es un grafo no dirigido y conexo, entonces:

G contiene un ciclo euleriano $\Leftrightarrow$ $\forall$ v $\in$ V(G), $d(v)$ es par.
\end{caminoeuleriano}

Los casos de prueba para los cuales la pregunta "¿hay circuito euleriano?" tiene como respuesta NO, serán aquellos
en los que el grafo no sea conexo, o tenga algún nodo de grado impar (por negación de la proposición de la derecha).

En el problema, no se consideran los nodos de grado 0 como nodos aislados, porque si no aparecen es porque ni siquiera
existe una cuenta con ese color. Dicho de otro modo, el grafo representado es isomorfo a uno con nodos de grado mayor que 0.


\begin{enumerate}
	% CASO 1:  NO TODOS PARES
	\item CASO 1:
	\begin{itemize}
		\item Algún nodo tiene grado impar;
	\end{itemize}

\begin{figure}[h]
	\centering
	\subfloat[Ej. de caso 1] {
	\begin{tikzpicture}
		\SetVertexNormal[Shape = circle,
							FillColor  = white]
		%\SetVertexNoLabel
		\SetUpEdge[lw         = 1pt,
						color      = black,
						labelcolor = white,
						labeltext  = black,
						labelstyle = {sloped,draw,text=black}]
						
		\Vertex[x=2, y=0]{2}
		\Vertex[x=4, y=0]{3}
		\Vertex[x=6, y=0]{4}
		\SetVertexNormal[Shape = circle,
							FillColor  = yellow]
		\Vertex[x=0, y=0]{1}
		\Vertex[x=8, y=0]{5}
		
		\tikzstyle{EdgeStyle}=[bend left]
		\Edges(1,2)
		\Edges(2,3)
		\Edges(3,4)
		\Edges(4,5)
	\end{tikzpicture}
	}
\end{figure}
\textbf{Salida esperada}: no hay circuito euleriano.
	\begin{verbatim}
		INPUT:
		1
		3
		1 2
		2 3
		3 4
		4 5

		OUTPUT:
		Case #1
		some beads may be lost
	\end{verbatim}

	% CASO 2: TODOS PARES, NO CONEXO, SIN HUECOS
	\item CASO 2:
	\begin{itemize}
		\item Todos los nodos tienen grado par
		\item El grafo no es conexo
		\item Las aristas recubren todos los nodos posibles (hay etiquetas de 1 a C)
	\end{itemize}
\begin{figure}[h]
	\centering
	\subfloat[Ej. de caso 2] {
	\begin{tikzpicture}
		\SetVertexNormal[Shape = circle,
							FillColor  = green]
		%\SetVertexNoLabel
		\SetUpEdge[lw         = 1pt,
						color      = black,
						labelcolor = white,
						labeltext  = black,
						labelstyle = {sloped,draw,text=black}]
						
		\Vertex[x=0, y=0]{1}
		\Vertex[x=2, y=0]{2}
		\Vertex[x=4, y=0]{3}
		\SetVertexNormal[Shape = circle,
							FillColor  = yellow]
		\Vertex[x=6, y=0]{4}
		\Vertex[x=8, y=0]{5}
		\Vertex[x=10, y=0]{6}
		
		\tikzstyle{EdgeStyle}=[bend left]
		\Edges(1,2)
		\Edges(2,3)
		\Edges(3,1)
		\Edges(4,5)
		\Edges(5,6)
		\Edges(6,4)
	\end{tikzpicture}
	}
\end{figure}	
	
\textbf{Salida esperada}: no hay circuito euleriano.

\begin{verbatim}
INPUT:
1
6
1 2
2 3
3 1
4 5
5 6
6 4

OUTPUT:
Case #1
some beads may be lost
\end{verbatim}


	% CASO 3: TODOS PARES, NO CONEXO, HAY HUECOS
	\item CASO 3:
	\begin{itemize}
		\item Todos los nodos tienen grado par
		\item El grafo no es conexo
		\item Hay nodos con grado 0 (hay etiquetas no presentes)
	\end{itemize}
	
\begin{figure}[h]
	\centering
	\subfloat[Ej. de caso 3 (faltan las etiquetas 1 y 5)] {
	\begin{tikzpicture}
		\SetVertexNormal[Shape = circle,
							FillColor  = green]
		%\SetVertexNoLabel
		\SetUpEdge[lw         = 1pt,
						color      = black,
						labelcolor = white,
						labeltext  = black,
						labelstyle = {sloped,draw,text=black}]
						
		\Vertex[x=2, y=0]{2}
		\Vertex[x=4, y=0]{3}
		\Vertex[x=6, y=0]{4}
		\SetVertexNormal[Shape = circle,
							FillColor  = yellow]
		\Vertex[x=10, y=0]{6}
		\Vertex[x=12, y=0]{7}
		\Vertex[x=14, y=0]{8}
		
		\tikzstyle{EdgeStyle}=[bend left]
		\Edges(2,3)
		\Edges(3,4)
		\Edges(4,2)
		\Edges(6,7)
		\Edges(7,8)
		\Edges(8,6)
	\end{tikzpicture}
	}
\end{figure}		
\textbf{Salida esperada}: no hay circuito euleriano.

\begin{verbatim}
INPUT:
1
6
2 3
3 4
4 2
6 7
7 8
8 6

OUTPUT:
Case #1
some beads may be lost
\end{verbatim}


\textbf{Bajo alguna de las anteriores condiciones, no hay circuito euleriano. En toda otra entrada, sí}
La dificultad recae en armar y devolver dicho circuito.

Los casos restantes son análogos a los casos 3 y 2.

	% CASO 4: TODOS PARES, CONEXO, HAY HUECOS
	\item CASO 4:
	\begin{itemize}
		\item Todos los nodos tienen grado par
		\item El grafo es conexo
		\item Hay nodos con grado 0 (hay etiquetas no presentes)
	\end{itemize}
	
\begin{figure}[h]
	\centering
	\subfloat[Ej. de caso 4 (faltan las etiquetas 1 y 5)] {
	\begin{tikzpicture}
		\SetVertexNormal[Shape = circle,
							FillColor  = green]
		%\SetVertexNoLabel
		\SetUpEdge[lw         = 1pt,
						color      = black,
						labelcolor = white,
						labeltext  = black,
						labelstyle = {sloped,draw,text=black}]
						
		\Vertex[x=2, y=0]{2}
		\Vertex[x=4, y=0]{3}
		\Vertex[x=6, y=0]{4}
		\Vertex[x=10, y=0]{6}
		\Vertex[x=12, y=0]{7}
		\Vertex[x=14, y=0]{8}
		
		\tikzstyle{EdgeStyle}=[bend left]
		\Edges(2,3)
		\Edges(3,4)
		\Edges(4,2)
		\Edges(4,6)
		\Edges(6,4)
		\Edges(6,7)
		\Edges(7,8)
		\Edges(8,6)
	\end{tikzpicture}
	}
\end{figure}		
\textbf{Salida esperada}: devolver el circuito euleriano.

\begin{verbatim}
INPUT:
1
8
2 3
3 4
4 2
6 7
7 8
8 6
4 6
6 4

OUTPUT:
Case #1
2 4
4 6
6 8
8 7
7 6
6 4
4 3
3 2
\end{verbatim}


	% CASO 5: TODOS PARES, CONEXO, SIN HUECOS
	\item CASO 5:
	\begin{itemize}
		\item Todos los nodos tienen grado par
		\item El grafo no es conexo
		\item Las aristas recubren todos los nodos posibles (hay etiquetas de 1 a C)
	\end{itemize}
\paragraph{}
\begin{figure}[h]
	\centering
	\subfloat[Ej. de caso 5] {
	\begin{tikzpicture}
		\SetVertexNormal[Shape = circle,
							FillColor  = green]
		%\SetVertexNoLabel
		\SetUpEdge[lw         = 1pt,
						color      = black,
						labelcolor = white,
						labeltext  = black,
						labelstyle = {sloped,draw,text=black}]
						
		\Vertex[x=0, y=0]{1}
		\Vertex[x=2, y=0]{2}
		\Vertex[x=4, y=0]{3}
		\Vertex[x=6, y=0]{4}
		\Vertex[x=8, y=0]{5}
		\Vertex[x=10, y=0]{6}
		
		\tikzstyle{EdgeStyle}=[bend left]
		\Edges(1,2)
		\Edges(2,3)
		\Edges(3,1)
		\Edges(4,5)
		\Edges(5,6)
		\Edges(5,2)
		\Edges(2,5)
		\Edges(6,4)
	\end{tikzpicture}
	}
\end{figure}	
	
\textbf{Salida esperada}: devolver el circuito euleriano.

\begin{verbatim}
INPUT:
1
8
1 2
2 3
3 1
4 5
5 6
6 4
5 2
2 5

OUTPUT:
Case #1
1 3
3 2
2 5
5 6
6 4
4 5
5 2
2 1
\end{verbatim}

\subsubsection{Casos de prueba de grafos eulerianos}

\begin{enumerate}
	\item Circuitos simples, con la entrada en distinto orden.
	\item Circuitos con \textit{loops} en nodos.
	\item Circuitos no-simples (\textit{tours})
\end{enumerate}

\paragraph{Circuitos simples, con la entrada en distinto orden}
\begin{verbatim}
INPUT:
2
3
4 5
5 6
6 4
3
6 5
6 4
5 4

OUTPUT:
Case #1
4 6
6 5
5 4

Case #2
4 5
5 6
6 4
\end{verbatim}
\textit{Es el mismo collar}

\paragraph{Circuitos con \textit{loops} en nodos.}
\begin{verbatim}
INPUT:
1
6
4 5
5 6
6 4
4 4
4 4
5 5

OUTPUT:
Case #1
4 6
6 5
5 5
5 4
4 4
4 4
\end{verbatim}
 
\paragraph{Circuitos no-simples (\textit{tours})}
\begin{verbatim}
INPUT:
1
9
4 5
5 6
6 7
8 6
8 7
6 4
4 4
4 4
5 5

OUTPUT:
Case #1
4 6
6 8
8 7
7 6
6 5
5 5
5 4
4 4
4 4
\end{verbatim}
	
\end{enumerate}


\subsection{Correctitud}

Nuestro programa es utiliza una implementación del algoritmo desarrollado por Hierholzer (1873), y que se detalla en la
bibliografía usada en la materia. Es el algoritmo 6.1.1 \footnote{ Gross J.L. - Yellen J. , \textit{Graph Theory and its applications 2nd}, en 6.1 Eulerian trails and tours}

\begin{algorithm}[H]
\caption{Algoritmo 6.1.1: Circuito Euleriano}
\mbox{\textit{Entrada}: un grafo conexo $G$ cuyos nodos tienen todos grado par}

\mbox{\textit{Salida}: un circuito euleriano $T$}
\begin{algorithmic}[1]
	\STATE Empezar en cualquier nodo $v$, y construir un camino cerrado $T$ en $G$
	\WHILE{ haya aristas de $G$ que no estén en el camino $T$ }
		\STATE Elegir un nodo $w$ en $T$ que sea incidente en una arista no visitada
		\STATE Comenzando en el nodo $w$, construir un camino cerrado $D$ de aristas no visitadas
		\STATE Alargar el camino $T$ anexándole $D$ a $T$ en el nodo $w$
	\ENDWHILE
	\RETURN $T$
\end{algorithmic}
\end{algorithm}
NOTA: \textit{camino} es usado en el sentido del texto original: \textit{trail}. Que es un camino que además no repite aristas, aunque sí nodos.

\paragraph{}

En primer lugar garantizamos que sea euleriano. Condiciones necesarias y suficientes:

\begin{itemize}
	\item El grafo es conexo.
	\item Todos los nodos del grafo tienen grado par.
\end{itemize}

Si no se satisface alguna de esas condiciones, no sólo no podemos aplicar el anterior algoritmo sino que
tampoco tiene un circuito euleriano.

El programa es correcto para casos negativos.

\paragraph{}
Si, en cambio, son verdaderos. Aplicamos el algoritmo que detallamos, y que asumimos correcto.
Lo único en que varía es lo que ya mencionamos anteriormente: el grafo de entrada no tiene nodos aislados,
tenemos que asegurarnos de ignorar dichos nodos en la implementación.

El programa es correcto para casos positivos.


\paragraph{Conclusión:} el programa es correcto.



\subsection{Mediciones}

\subsubsection{Peor caso}
Aunque la complejidad del algoritmo es siempre $O(N + C)$ ya que es el tiempo que le toma al algoritmo armar el grafo, en la práctica
se tendría un peor caso cuando el grafo sea euleriano ya que en dicho caso se tiene que ejecutar la función circuitoEuleriano que
construye el circuito.

\mifig{problema1/peor}{Peor caso}

\subsubsection{Mejor caso}
Por lo anterior, ocurre cuando el grafo no es euleriano y en particular cuando no es conexo, ya que en ese caso el BFS no revisa
todos los nodos. Los casos generados para esta medición son cuentas que tienen sus dos colores iguales y por lo tanto en el grafo
asociado las únicas aristas presentes son ``rulos'', y debido a esto el algoritmo de BFS solamente revisa un nodo, sin importar cual.

\mifig{problema1/mejor}{Mejor caso}

\subsubsection{Casos aleatorios}
Casos aleatorios con $C$ fijo en 50 y variando $N$.

\mifig{problema1/aleatorio-vfijo}{Casos aleatorios ($C$ fijo)}


\newpage
